//
// Created by lxinp on 2022/8/17.
//

#include <iostream>
#include <cassert>
#include "heap.h"


template<typename T>
Heap<T>::Heap() : n(0), max_size(4) {
    arr = new T[max_size+1];
}


template<typename T>
Heap<T>::~Heap() {
    delete[] arr;
}


template<typename T>
Heap<T>::Heap(const T* array, int length) : n(length), max_size(length) {
    arr = new T[max_size+1];
    // Copy elements into the internal array
    for (int i=0; i<length; i++) arr[i+1] = array[i];
    // Heapify down the first half
    for (int i=n/2; i>0; i--) heapify_down(i);
}


template<typename T>
T Heap<T>::get_min() {
    return arr[1];
}


template<typename T>
void Heap<T>::remove_top() {
    assert(!is_empty());
    arr[1] = arr[n--];
    heapify_down(1);
}


template<typename T>
void Heap<T>::insert(const T& data) {
    if (is_full()) resize();
    arr[++n] = data;
    heapify_up(n);
}


template<typename T>
int Heap<T>::size() const {
    return n;
}


template<typename T>
void Heap<T>::print() const {
    std::cout << "[";
    for (int i=1; i<n; i++) {
        std::cout << arr[i] << ", ";
    }
    std::cout << arr[n] << "]" << std::endl;
}


template<typename T>
void Heap<T>::resize() {
    max_size *= 2;
    T* temp = arr;
    arr = new T[max_size+1];
    for (int i=1; i<=n; i++) {
        arr[i] = temp[i];
    }
    delete[] temp;
}


template<typename T>
bool Heap<T>::is_empty() const {
    return n == 0;
}


template<typename T>
bool Heap<T>::is_full() const {
    return n == max_size;
}


template<typename T>
void Heap<T>::heapify_up(int loc) {
    if (loc == 1) return;
    int parent = loc / 2;
    if (arr[parent]>arr[loc]) {
        std::swap(arr[parent], arr[loc]);
        heapify_up(parent);
    }
}


template<typename T>
void Heap<T>::heapify_down(int loc) {
    int s = loc;
    int left = loc*2;
    int right = left+1;

    if (left <= n && arr[s]>arr[left]) {  // check if left child exists
        s = left;
    }
    if (right <= n && arr[s]>arr[right]) {  // check if right child exists
        s = right;
    }
    if (s != loc) {  // s is the smallest of the 3 nodes
        std::swap(arr[loc], arr[s]);
        heapify_down(s);
    }
}


template class Heap<int>;
